/*
提交链接:https://leetcode.cn/problems/minimum-number-of-refueling-stops/description/
871. 最低加油次数
赖德檀 2024/12/19
*/

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        stations.push_back({target,0});
        priority_queue<int>qe;
        int sum=0,ans=0,k=startFuel;
        for(int i=0;i<stations.size();i++)
        {
            k-=stations[i][0]-sum;
            while(!qe.empty()&&k<0)
            {
                k+=qe.top();
                qe.pop();
                ans++;
            }
            if(k<0) return -1;
            sum=stations[i][0];
            qe.push(stations[i][1]);
        }
        return ans;
    }
};